package com.tree;

import java.util.Arrays;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 根据前序和中序构造树
 *  * 主要是掌握Arrays.copyOfRange(original,from,to); 这个函数，然后递归就行，这个函数包含from 但是不包含to
 * @date 2022/8/27 17:54
 */
public class BuildTreeByPreAndIn {
    /**
     * Definition for a binary tree node.
     * */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder);
    }

    public  TreeNode build(int[] preOrder, int[] inOrder) {
        if(inOrder.length<=0){
            return null;
        }
        if(inOrder.length==1){
            return  new TreeNode(inOrder[0]);
        }
        TreeNode root=new TreeNode(preOrder[0]);
        for (int i = 0; i < inOrder.length; i++) {
            if(preOrder[0]==inOrder[i]){
                int[] leftInOrder= Arrays.copyOfRange(inOrder,0,i);
                int[] leftPreOrder=Arrays.copyOfRange(preOrder,1,i+1);
                int[] rightInOrder= Arrays.copyOfRange(inOrder,i+1,inOrder.length);
                int[] rightPreOrder= Arrays.copyOfRange(preOrder,i+1,preOrder.length);
                root.left=build(leftPreOrder,leftInOrder);
                root.left=build(rightPreOrder,rightInOrder);
                break;
            }
        }

        return root;
    }
}
